void solve()
{
  ll a, b;
  cin >> a >> b;

  vl primes, cnt;
  ll n = a;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      cnt.pb(0);
      primes.pb(i);
      while (n % i == 0) {
        n /= i;
        cnt.back()++;
      }
    }
  }
  if (n > 1) {
    cnt.pb(1);
    primes.pb(n);
  }
  auto dfs = [&](auto &&dfs, ll v) -> ll {
    if (!v) {
      return 0ll;
    }
    ll mx = 0, mv = -1;
    rep(i, 0, sz(cnt) - 1) {
      if (!cnt[i] || v < primes[i]) {
        continue;
      }
      ll r = v / primes[i] * primes[i];
      if (mx < r) {
        mx = r;
        mv = i;
      }
    }
    if (mv == -1) {
      return v;
    }
    cnt[mv]--;
    return dfs(dfs, mx / primes[mv]) + (v - mx);
  };
  cout << dfs(dfs, b);
}